With regard to computers, garbage collection refers to a process of identifying unused areas of main memory storage. In object-oriented computing languages, the computer executing the program allocates memory for each of the objects. A Java Virtual Machine (JVM) using the object oriented programming language Java allocates memory for the instantiation of the objects from a free memory area called a heap. Memory is allocated to, and freed from, the heap in blocks of one of a number of predetermined sizes. Eventually, when the objects are no longer being referenced by the program, the memory allocated for the created objects is reclaimed through a process called garbage collection. The garbage collection process clears the objects from memory such that the once allocated memory is again available for use. More particularly, a garbage collection process involves automatically determining which blocks of memory can be freed, marking unused blocks as no longer needed by an application, collecting all of the unused blocks of memory at periodic intervals, returning the unused blocks to the heap, and marking the blocks as free for use. Such a garbage collection process is often referred to as a mark-and-sweep since unused portions of memory are marked as garbage during a mark phase and then removed from allocated memory in a sweep phase. Although the process of garbage collection frees memory it may be problematic in applications where its unpredictable consumption of processor time affects the running of the application. In addition, the constant allocating and freeing of blocks of memory tends to fragment the memory over time.
The exact garbage collection strategy used by an object oriented program will often vary depending on the type of system in which the program is executing. For example, in some JVM implementations, the garbage collector is a built-in component. In other applications, different garbage collectors may be plugged in for different circumstances. Many different algorithms have been employed in these different garbage collector implementations. For example, server applications in a multi-user multiprocessor environment tend to have a memory-use profile that differs from a desktop computer environment. Furthermore, embedded-Java devices such as cell phones and handheld devices have different memory-use profiles. A single garbage collector is typically designed to implement one particular strategy and cannot be modified “on-the-fly” to change its strategy. Therefore, a customized garbage collector must typically be built into each programming instance depending upon the computer platform and operating environment in which the program is executing. On any given day, a particular set of garbage collection characteristics or garbage collection algorithm metrics will be better for one device but not for another device. For example, a device with a small amount of memory may require a very aggressive garbage collection routine whereas as a large server with lots of memory may permit a more relaxed approach. In each case, a different type of garbage collection algorithm is needed in order to adapt the performance of the garbage collector to the performance characteristics of the hardware platform. Therefore, what is needed is a garbage collection process that can be easily be tuned for a variety of particular applications.
There are several common techniques for garbage collection. One technique is referred to as “copying” and relates to logically dividing the memory in half and using only one half of the memory at a time. During garbage collection, the collection routine copies all live objects to the other half of the memory. Following the copying of all the live objects, the memory manager adds the entire first half of memory to the free list. Consequently, the previously used memory which contained both the live objects and the garbage objects becomes free memory. In other words, the garbage filled memory has been reclaimed for later use. Another garbage collection technique is the mark-and-sweep method. The mark-and-sweep technique marks all live objects of memory. Each memory object usable by a program application is marked as used by the garbage collector. The garbage collector then sweeps the entire heap to reclaim all unmarked objects of memory by adding the unmarked objects to the free list. When the sweep phase is complete, all garbage objects are now on the free list and available to be reallocated to a computer program.
In some instances, the mark-and-sweep technique might be preferred over the copying technique because it is faster than copying, since the copying of objects and updating the references takes more time than adding a garbage block to a free list. Moreover, the mark-and-sweep technique is often more space efficient since it uses the whole memory, as opposed to only half, as used in the copying technique. However, in other situations, the copying technique may be preferred due to the lack of fragmentation and in instances having a relatively small number of live memory blocks.
Unfortunately, the mark-and-sweep technique has disadvantages. One such disadvantage is that the sweep function of the mark-and-sweep technique examines every single memory block. This is time consuming if the number of live objects is low relative to the number of objects allocated. In particular, some applications such as anti-lock brake management system are real time applications in that they require that a primary application never stop running. In such an application, it is important that the amount of processor time and memory devoted to garbage collection not interrupt the running of the application or mutator. In addition, it is important that the memory not be fragmented to the point that a certain level of memory is not available for the primary application. Unfortunately, prior art garbage collection routines cannot guarantee a given level of performance. Therefore, what is needed is a real time garbage collection algorithm with guaranteed performance that allows for managed defragmentation of the memory.